package com.wfm.leetcode.editor.cn;

import com.wfm.common.TreeNode;
import java.util.ArrayList;
import org.junit.Test;

/**
 *     1
 *    2  3
 *  4  5 6 7
 * 最终得到右下角的7
 * 7号节点一直除以2，余数(7%2)=1,(3%2)=1
 * 6号节点一直除以2，余数(6%2)=0,(3%2)=1
 * 找到规律：将这些余数逆序，遇到1向右，遇到0向左
 * https://blog.csdn.net/wangbaochu/article/details/53861914
 */
public class P完全二叉树的最底最右节点 {

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.generatorTreeNode("1,2,3,4,5,6,7");
        TreeNode bottomRight = new P完全二叉树的最底最右节点().getBottomRight(treeNode);
        System.out.println(bottomRight.val);
    }
    public TreeNode getBottomRight(TreeNode root){
        TreeNode res = root;
        int[] seq = getSeq(getCnt(root,0));
        for (int i = 0; i <seq.length; i++) {
            int i1 = seq[i];
            if(i1==1){
                res=res.right;
            }else if(i1==0){
                res=res.left;
            }
        }
        return res;
    }
    public int[] getSeq(int num){
        ArrayList<Integer> res = new ArrayList<>();
        while (num/2!=0){
            res.add(num%2);
            num=num/2;
        }
        int[] r = new int[res.size()];
        for (int i = 0; i < r.length; i++) {
            r[i]=res.get(res.size()-1-i);
        }
        return r;
    }
    public int getCnt(TreeNode root,int res){
        if(root==null){
          return res;
        }
        return 1+getCnt(root.left,res)+getCnt(root.right,res);
    }
    @Test
    public void test(){
        TreeNode treeNode = TreeNode.generatorTreeNode("1,2,3,4,5,6,7");
        int cnt = getCnt(treeNode,0);
        System.out.println(cnt);
    }
}
